#孩子表示法

class LNode:
    '''链表'''
    def __init__(self, value=None, _next=None):
        self.value = value
        self.next = _next
    def append(self,value):
        '''在链表的尾部添加节点。'''
        if not self.value:
            self.value = value
        else:
            node=LNode(value)
            cur = self
            while cur.next:
                cur = cur.next
            cur.next = node
    def search(self, value):
        '''查找指定的元素值是否在链表中'''
        cur = self
        while cur:
            if cur.value == value:
                return True
            else:
                cur = cur.next
        return False
    def travel(self):
        '''遍历整个链表'''
        cur = self
        while cur is not None:
            yield cur.value
            cur = cur.next
    def __str__(self):
        lst=[]
        cur = self
        while cur:
            lst.append(cur.value)
            cur = cur.next
        return f'LNode:{lst}'

class CTree:
    '''使用 “孩子表示法” 来存储和表示多叉树'''
    class CTNode:
        def __init__(self, value):
            self.value = value  # 节点的数据域
            self.children = LNode()  # 节点的子节点组成的单链表
        def __str__(self):
            return f'CTNode:{self.value}'

    def __init__(self):
        self.data = []
    def __str__(self):
        lst=[i.value for i in self.data]
        return f'CTree:{lst}'
    def add(self, data, parent):
        '''添加节点
            data: 节点的数据域
            parent: 节点的父节点的下标
        '''
        node = self.CTNode(data)
        if parent == -1:  # 要添加是根节点
            if not self.data:
                self.data.append(node)
            else: raise '树已经有根节点了，不能再添加节点'
        else:
            try:
                self.data.append(node)
                node_index = self.data.index(node)  # 新添加节点的下标
                self.data[parent].children.append(node_index)
            except IndexError as e:
                raise '节点的父节点不存在，非法插入'

    def parent(self, data):
        '''获取节点的父节点'''
        node = None  # 要查询的节点是哪个
        for i in self.data:
            if i.value == data:
                node = i
                break
        if not node:
            raise "节点不存在"
        node_index = self.data.index(node)
        if node_index == 0:
            return None
        else:
            for j in self.data:
                if j.children.search(node_index):
                    return j

    def children(self, data):
        '''获取节点的所有子节点'''
        node = None  # 要查询的节点是哪个
        for i in self.data:
            if i.value == data:
                node = i
                gen = node.children.travel()  # 遍历孩子单链表
                return [self.data[j] for j in gen]
        if not node:
            raise "节点不存在"


if __name__ == '__main__':
    t = CTree()
    t.add('A', -1)
    t.add('B', 0)
    t.add('C', 0)
    t.add('D', 1)
    t.add('E', 2)
    t.add('F', 2)
    t.add('G', 3)
    t.add('H', 3)
    t.add('I', 3)
    t.add('J', 4)

    print(t)
    print(t.data[3].children)

    node= t.parent('B')
    print(node)

    c=t.children('D')
    print([i.value for i in c])